import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author Kevin
 * @Data 2021/4/26
 */

/*
    设G=（VN，VT，P，S）
    0型文法：如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)且至少含有一个非终结符，而β∈(VN∪VT)，则G是一个0型文法
    1型文法：它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。注意：虽然要求|β|>=|α|，但有一特例：α→ε也满足1型文法。
    2型文法：也叫上下文无关文法，它对应于下推自动机。2型文法是在1型文法的基础上,再满足：每一个α→β都有α是非终结符。如A->Ba,符合2型文法要求。
    3型文法：也叫正规文法，它对应于有限状态自动机。它是在2型文法的基础上满足:A→α|αB（右线性）或A→α|Bα（左线性）。
 */
/*
    3型文法遵循什么规范呢？
    第一点：左边必须只有一个字符，且必须是非终结符；
    第二点：其右边最多只能有两个字符，且当有两个字符时必须有一个为终结符而另一个为非终结符。当右边只有一个字符时，此字符必须为终结符。
    第三点：对于3型文法中的所有产生式，其右边有两个字符的产生式，这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定，也就是说如果一个产生式右边的两个字符的排列是：终结符＋非终结符，那么所有产生式右边只要有两个字符的，都必须前面是终结符而后面是非终结符。反之亦然，要么，就全是：非终结符＋终结符。

    依以上规则判断，你所给的三个文法显然都不属于3型文法。

    再看2型文法如何判断：
    第一点：与3型文法的第一点相同，即：左边必须有且仅有一个非终结符。
    第二点：2型文法所有产生式的右边可以含有若干个终结符和非终结符（只要是有限的就行，没有个数限制）。

    依2型文法的判断规则，你的三个文法都属于2型文法，即：上下文无关文法。

    再看1型文法如何判断：
    第一点：1型文法所有产生式左边可以含有一个、两个或两个以上的字符，但其中必须至少有一个非终结符。
    第二点：与2型文法第二点相同。

    依1型文法判断规则，显然，你的文法也是属于1型的。

    最后是0型文法，这个就不用看了，只要你能描述出来，都属于这个类型，即0型。

    所以，取其最高的符合规则，最后的答案是其符合：上下文无关文法规则，即2型。
 */
public class 判断文法 {
    public static void main(String[] args) {
        while (true){
            Scanner scanner = new Scanner(System.in);
            System.out.println("请输入文法：");
            String s = scanner.next();
            judgeGrammar(s);
        }
    }
    public static void judgeGrammar(String s) {
        //java正则表达式来匹配输入的文法是那种类型
        Pattern p3 = Pattern.compile("[A-Z]::=(([A-Z][a-z])|([a-z][A-Z])|[a-z])");
        Matcher m3 = p3.matcher(s);
        boolean b3 = m3.matches();
        if (b3) {
            System.out.println("三型文法");
        }else{
            Pattern p2 = Pattern.compile("[A-Z]::=[a-zA-Z]++");
            Matcher m2 = p2.matcher(s);
            boolean b2 = m2.matches();
            if(b2){
                System.out.println("二型文法");
            }else{
                Pattern p1 = Pattern.compile("[a-z]*+[A-Z]++[a-z]*+::=[a-zA-Z]++");
                Matcher m1 = p1.matcher(s);
                boolean b1 = m1.matches();
                if(b1){
                    System.out.println("一型文法");
                }else{
                    Pattern p0 = Pattern.compile("[a-z]*+[A-Z]*+[a-z]*+::=[a-zA-Z]++");
                    Matcher m0 = p0.matcher(s);
                    boolean b0 = m0.matches();
                    if (b0){
                        System.out.println("0型文法");
                    }else{
                        System.out.println("请检查你的输入是否为文法");
                    }
                }
            }
        }
    }
}
